The disclosed configuration relates to electronic design automation and, more particularly, to methods and apparatuses for automatic legalization of a multi-patterning integrated circuit layout.
Advancements in process technology have impacted integrated circuit manufacturing in at least two key ways. Firstly, scaling of device geometry achieved through sub-wavelength lithography has facilitated the packing of more devices on a chip. Secondly, different process recipes have enabled the manufacturing of heterogeneous devices with different threshold and supply voltages on the same die. A consequence of these improvements, however, has been an explosion in the number of design rules that need to be obeyed in the layout. Instead of simple width and spacing rules, modern fabrication technologies prescribe complex contextual rules that have to be obeyed for manufacturability.
The increase in the number of rules has complicated the task of creating design rule clean layouts, i.e., layouts that do not have design rule violations. Creating design rule clean layouts for digital circuit designs can be facilitated by the use of standard cell layouts as building blocks, and placement and routing tools that are extended to address the design rules.
Unfortunately, this approach usually does not work for analog, RF and custom circuit designs. Layouts for such designs are typically created manually using layout editors, and, because of the number and complexity of the design rules, checking and fixing them is a laborious process.
A conventional design rule check (DRC) system requires a powerful two-dimensional geometry engine which supports geometric operations such as Boolean operations like AND, OR, NOT, XOR; sizing operations like grow/shrink horizontal/vertical/diagonal; other operations like merge, shift, flip, cut, smooth; as well as all-angle geometry for true Euclidean distance calculations. Individual rules are typically checked individually over an entire layout region. This is also true of individual rule values of same rule (e.g. a check against the minimum value for a rule, and another check against a preferred value for the same rule). Each check basically runs an independent sequence of geometry operations and numerous passes through the layout region are required.
Recently, the march toward increasingly smaller technology nodes has pushed fabrication vendors to support double-patterning technology (DPT). If integrated circuit features on a layer are laid out too near each other for adequate separation when exposed through a lithographic mask, then the features are apportioned onto two different masks, each mask having only some of the features for the layer. During fabrication, the wafer is exposed twice, once with each mask. In this way features can be defined on the integrated circuit which are too finely spaced to be defined clearly and reliably by a single mask. Double-patterning technology can be extended to triple-patterning technology, in which the features for a layer are apportioned onto three different masks, and so on. Apportionment onto higher numbers of masks is possible as well, and these techniques are sometimes referred to generally as “multi-patterning technology”.
Typically the mask fabricator (which often is also the chip fabricator) uses its own algorithm to allocate shapes among the two or more masks. However, in some arrangements of layout shapes an allocation is not possible since a particular shape cannot be allocated to any of the masks without violating the spacing rules for features on that mask. In a layout layer which has not yet been split, these situations can be detected by a design rule checking algorithm which assigns different “colors” (corresponding to different lithographic masks) to any pair of shapes which are nearer to each other than the minimum multi-patterning spacing constraint for a single mask. Chains of such features are detected, each feature forcing the next feature to have a different color. In the double-patterning case, each next feature is assigned the color opposite to the former feature in the chain. In the multi-patterning case multiple colors are used and it is sufficient that each next feature be assigned a different (also called non-conflicting) color.
If a chain loops back onto itself, it forms a “cycle”. A cycle itself is not bad, unless there is no way to avoid two adjacent features in the chain being assigned the same color. In the double-patterning situation, there is no conflict if a cycle contains an even number of features because a color conflict can be avoided. The arrangement can then be allocated among the two masks without violating the single-mask spacing rules. If a cycle contains an odd number of features in the double-patterning case, however, then a coloring conflict exists and the arrangement, if not modified, cannot be allocated among the two masks without violating the single-mask spacing rules. The latter situation is sometimes referred to herein as a “DPT odd cycle violation” or “DPT odd cycle conflict”. (In the extension to multi-patterning, coloring conflicts are sometimes referred to herein as “multi-patterning coloring violations”.)
A number of techniques exist for handling odd cycle violations. But if none of them work one or more of the features must be moved away from one or more other features in order to break the cycle. Since this solution can reduce circuit density, it would be desirable to move features only as far as needed in order to solve the problem. For a manual layout editor, this would ideally involve real time DPT odd cycle detection, so that after every movement or other editing of a shape the user can see immediately whether the violation remains. But checking and fixing for DPT odd cycle conflicts can be extremely time-consuming by conventional methods, and prohibitively slow for such real time layout editing because in conventional methods there is a lot of trial and error involved. Some modifications can lead to new conflicts, so one may have to go back and forth many times. Even if it is not real time, it is the iterative process that takes too long because of the local view of layout. Also, if the edits a more global in nature, i.e., looking at all conflicts instead of one by one, it can be arrived at a layout with better area usage.
Therefore, there is a need for an improved concept providing a robust solution to the problem of layout editing, in a manner that avoids and fixes double-patterning or multi-patterning conflicts.